#include<iostream>

using namespace std;


template<class DataType>
struct Node {
    DataType data;                // 存储数据
    Node<DataType> *next;        // 存储下一个结点的地址
};

template<class DataType>
class LinkList {
public:
    LinkList();

    LinkList(DataType a[], int n);

    ~LinkList();

    int Length();

    DataType Get(int i);

    int Locate(DataType x);

    void Insert(int i, DataType x);

    DataType Delete(int i);

    void PrintList();

private:
    Node<DataType> *first;
};

template<class DataType>
LinkList<DataType>::LinkList() {
    first = new Node<DataType>;
    first->next = NULL;
}

/*
头插法创建链表
头插法是在新创建结点的头部插入下一个新创建的结点
尾插法是在新创建结点的尾部插入下一个新创建的结点
*/
template<class DataType>
LinkList<DataType>::LinkList(DataType a[], int n) {
    // 头结点
    first = new Node<DataType>;
    first->next = NULL;
    for (int i = 0; i < n; i++) {
        Node<DataType> *s = new Node<DataType>;
        s->data = a[i];
        s->next = first->next;
        first->next = s;
    }
}

/*
尾插法
*/
//template <class DataType>
//LinkList<DataType>::LinkList(DataType a[], int n) {
//    first = new Node<DataType>;
//    Node<DataType>* r = first;
//    for (int i = 0; i < n; i++)
//    {
//        Node<DataType>* s = new Node<DataType>;
//        s->data = a[i];
//        r->next = s;
//        r = s;
//    }
//    r->next = NULL;
//}

/*
单链表类中的结点是用new申请的，在释放的时候无法自动释放，所以，析构函数要将单链表中的结点空间释放
*/
template<class DataType>
LinkList<DataType>::~LinkList() {
    while (first != NULL) {
        Node<DataType> *q = first;
        first = first->next;
        delete q;
    }
}

/*
计算长度
*/
template<class DataType>
int LinkList<DataType>::Length() {
    Node<DataType> *p = first->next;
    int count = 0;
    while (p != NULL) {
        p = p->next;
        count++;
    }
    return count;
}

template<class DataType>
DataType LinkList<DataType>::Get(int i) {
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL && count < i) {
        p = p->next;
        count++;
    }
    if (p == NULL) {
        throw "Location";
    } else {
        return p->data;
    }
}

template<class DataType>
int LinkList<DataType>::Locate(DataType x) {
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL) {
        if (p->data == x) return count;
        p = p->next;
        count++;
    }
    return 0;
}

template<class DataType>
void LinkList<DataType>::Insert(int i, DataType x) {
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count < i - 1) {
        p = p->next;
        count++;
    }
    if (p == NULL) throw "Location Error";
    else {
        Node<DataType> *s = new Node<DataType>;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

template<class DataType>
DataType LinkList<DataType>::Delete(int i) {
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count < i - 1) {
        p = p->next;
        count++;
    }
    if (p == NULL || p->next == NULL) throw "Location Error";
    else {
        Node<DataType> *q = p->next;
        int x = q->data;
        p->next = q->next;
        return x;
    }
}

template<class DataType>
void LinkList<DataType>::PrintList() {
    Node<DataType> *p = first;
    while (p!=NULL){
        cout<<p->data<<endl;
        p = p->next;
    }
}


int main(){
    LinkList<int> p;
    p.Insert(1,9);
    p.Insert(2,3);
    p.PrintList();
    p.Insert(3,6);
    p.PrintList();
    cout<<p.Get(2)<<endl;
    cout<<p.Locate(2)<<endl;
    cout<<p.Length()<<endl;
    p.Delete(1);
    p.PrintList();
    return 0;
}